#include <iostream>
using namespace std;
// 希尔排序
void ShellSort(int* a, int n) {
    // 确定我们的步长，然后进行各个组之间的插入排序，最后会退化成为直接插入排序
    for(int i = n / 2; i > 0; i /= 2) {
        for(int j = i; j < n; j++) {
            int temp = a[j];
            int t = j;
            while (t >= i && a[t - i] > temp) {
                a[t] = a[t - i];
                t -= i;
            }
            a[t] = temp;
        }
    }
}
int main() {
    int a[10] = {1, 4, 3, 5, 6, 3, 2, 7, 8, 0};
    ShellSort(a, 10);
    for(int i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}